Users of a computer system typically define processes to be performed by the system in a source language program. Program translation tools, such as compilers, linkers, and assemblers, can be used to convert the source language program to machine executable form. The utilization of computer resources can be minimized if the translation tools optimize the program during this conversion.
A typical program usually includes one or more execution loops to perform specific processing task more than once. Coding repeated processing steps as a loop reduces the size of the program. However, loops tend to increase execution time, since additional instructions are required to cycle through the loop, and to detect loop terminating conditions.
Some translation tools attempt to optimize loops simply by duplicating the instructions of the loop in-line so that the instructions can be executed strictly sequentially. "In-lining" may be a reasonable solution for loops with a small number of cycles. However, for loops which cycle a large number of times, in-lining is not a viable solution.
In addition, unless cache behavior is considered, in-lining can have unpredictable and sometimes detrimental effects on the performance of the cache. Also, simply duplicating instructions can overwhelm existing optimizing techniques, sometimes causing them to stop functioning, or confusing the optimization to the point that performance is actually degraded.
In another loop optimization technique, attempts are made to detect and move "invariant" code. Invariant code are any instructions of the loop which do not change the state of the computer system while executing the loop. Moving the invariant code from the loop can significantly decreases processing time. Invariant code can be detected by examining the operator and operands of the instructions of the program. Mechanisms which detect invariant code in simple loops are well understood.
However, most know optimizing techniques have problems recognizing the exact span of complex loop, such as nested loops and intersecting loops. Nested loops are loops within loops, and intersecting loops are loops which may be executed from more than one point external to the loop. Thus, known optimizing techniques can always capitalise on all invariant code motion opportunities.
Therefore, there is a need for an optimizing technique which can accurately determine the full span of loops within a program, and move invariant code across loop boundaries to increase processing efficiencies.